package com.LeetCode.Tree;

import org.junit.Test;

public class lowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left , p ,q);
        TreeNode right = lowestCommonAncestor(root.right, p ,q);

        //公共祖先不在左边
        if(left == null){
            return right;
        }
        //公共祖先不在右边
        if(right == null){
            return left;
        }

        return root;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p , TreeNode q){
        if(root == null) return null;
        if(root == p || root == q) return root;

        TreeNode node = root;

        while(node!=null){
            if(node.val < p.val && node.val < q.val){
                node = node.right;
            }else if(node.val > p.val && node.val > q.val){
                node = node.left;
            }else{
                return node;
            }
        }
        return null;
    }

    @Test
    public void test(){

    }
}
